# 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
#  字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
#
#  示例 1:
# 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
# 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
#
#  示例 2:
# 输入: strs = [""]
# 输出: [[""]]
#
#  示例 3:
# 输入: strs = ["a"]
# 输出: [["a"]]
#  提示：
#  1 <= strs.length <= 10⁴
#  0 <= strs[i].length <= 100
#  strs[i] 仅包含小写字母
from typing import List
import collections


class Solution:
    def groupAnagrams2(self, strs: List[str]) -> List[List[str]]:
        """
        排序 + 字典
        如果某些单词是字母异位词，则这些单词经过排序后一定完全相同
        于是可以想到用排序好了的单词作为key , 所有异位词组成的list为value形成字典

        遍历每个单词对其进行排序，然后判断排序后的单词是否在字典中
            是：直接在value的list后追加当前的单词
            否：创建新 K-V 键值对
        :param strs:
        :return:
        """
        # 简单写法
        map = collections.defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            map[key].append(s)
        return list(map.values())
        # 复杂写法
        # map = {}
        # for s in strs:
        #     sortedStr = str(sorted(s))
        #     if sortedStr in map:
        #         map[sortedStr].append(s)
        #     else:
        #         tmpList = []
        #         tmpList.append(s)
        #         map[sortedStr] = tmpList
        # return list(map.values())

    def groupAnagrams1(self, strs: List[str]) -> List[List[str]]:
        """
        计数 + 字典
        如果某些单词是字母异位词，则这些单词每个单词出现的次数是相同的
        于是可以想到用统计了每个字母个数的字符串(a-z的顺序)作为key , 所有异位词组成的list为value形成字典

        遍历每个单词对其进行字母计数并生成字符串，然后判断排序后的单词是否在字典中
            是：直接在value的list后追加当前的单词
            否：创建新 K-V 键值对

        :param strs:
        :return:
        """
        map = collections.defaultdict(list)
        for s in strs:
            counts = [0] * 26  # 26个 0 的list
            # 统计当前单词的各个字母出现的次数
            for ch in s:
                counts[ord(ch) - ord('a')] += 1
            # 将当前单词加入到对应的 K-V 中
            map[str(counts)].append(s)

        return list(map.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        return self.groupAnagrams2(strs)


if __name__ == "__main__":
    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    print(Solution().groupAnagrams(strs))
